import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class demo2 {
    /**
     * 347.前 k 个高频元素
     * https://leetcode.cn/problems/top-k-frequent-elements/description/
     */
    public int[] topKFrequent(int[] nums, int k) {
        // 1.使用 HashMap 对其所以 数据 出现的次数进行计数统计
        Map<Integer,Integer> hash = new HashMap<>();
        for(int num : nums) {
            hash.put(num,hash.getOrDefault(num,0) + 1);
        }

        // 2.创建一个小根堆，根据数组中的第二个也就是num出现的次数进行比较，使用小根堆可以得到最大的k数据
        // 这里存在的是数据，而非出现的次数
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> {
            // 根据每个数据的出现次数进行排序
            return hash.get(a) - hash.get(b);
        });
        // 3.根据出现的次数进行比较进而放入到堆中把对应的 key值
        for(Integer key : hash.keySet()) {
            if(queue.size() < k) {
                // 先把 堆 中的数据填k个
                queue.add(key);
            }else {
                // 如果当前的 key 在hash中对应的次数是大于 堆 顶数据所对应hash中的次数，那么就把key放入到堆中，并把堆顶数据进行 出堆
                if(hash.get(key) > hash.get(queue.peek())) {
                    queue.poll();
                    queue.add(key);
                }
            }
        }
        // 这个时候 堆 中所存放的数据，就是出现次数最高的 k个数
        int[] ret = new int[k];
        int index = 0;
        while(!queue.isEmpty()) {
            ret[index++] = queue.poll();
        }
        return ret;
    }
}
